// https://leetcode.cn/problems/n-th-tribonacci-number/

// 题干：泰波那契序列 Tn 定义如下：
//      T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
//      给你整数 n，请返回第 n 个泰波那契数 Tn 的值

// 示例：输入：n = 4
//      输出：4

// 碎语：正式迈入dp大门的第一题！万事开头难，坚持就是胜利！
//       dp的一般流程
//      1.状态表示，即创立一个dp表，里面的dp[i]就是状态表示 PS:非常重要，要努力
//      2.状态转移方程 dp[i]是什么，方程就怎么写，想着用前面的状态来求问题
//      3.初始化，保证填表的时候不越界
//      4.为了填写当前状态的时候，所需要的状态已经计算过了
//      5.返回值 题目要求+状态表示

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int tribonacci(int n)
    {
        // dp表里面的值所表示的含义怎么来？
        // 题目要求 经验+题目要求 分析问题的过程中，发现重复子问题
        // 本题中，dp[i]表示第i个泰波那契数的值，保证填表的时候别越界
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;

        // 1.创建dp表
        vector<int> dp(n + 1);

        // 2.初始化
        dp[0] = 0, dp[1] = dp[2] = 1;

        // 3.填表
        for (int i = 3 ; i < n + 1 ; i++)
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];

        // 4.返回值
        return dp[n];
    }
};

int main()
{
    Solution sol;
    cout << sol.tribonacci(5) << endl;
    
    return 0;
}